package com.xj.algorithm.leetcode;

/**
 * 回文链表
 */
public class L234_回文链表 {

    /**
     * 请判断一个链表是否为回文链表。
     *
     * 示例 1:
     *
     * 输入: 1->2
     * 输出: false
     * 示例 2:
     *
     * 输入: 1->2->2->1
     * 输出: true
     * 进阶：
     * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     */

    public static void main(String[] args) {
        ListNode root=new ListNode(1);
        root.next=new ListNode(2);
        System.out.println(isPalindromeGood(root));

        ListNode root2=new ListNode(1);
        root2.next=new ListNode(2);
        root2.next.next=new ListNode(2);
        root2.next.next.next=new ListNode(1);
        System.out.println(isPalindromeGood(root2));
    }

    //自己的解法：创建一个新链表然后再比较
    public static boolean isPalindrome(ListNode head) {
        ListNode root=null;
        ListNode index=head;

        while (index!=null){
            ListNode tmp=new ListNode(index.val);
            tmp.next=root;
            root=tmp;

            index=index.next;
        }

        while (head!=null){
            if(head.val!=root.val){
                return false;
            }
            head=head.next;
            root=root.next;
        }
        return true;
    }

    //精彩解法：快慢指针。将前半部分反转，然后和后半部分比较
    //最后slow变成了后半部分的第一个指针，pre变成了前半部分的颠倒后的第一个指针
    public static boolean isPalindromeGood(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }

        if(fast != null) {
            slow = slow.next;
        }

        while(pre != null && slow != null) {
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }

        return true;
    }
}